//两数相加（链表逆序）
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        int sum = 0;
        ListNode* phead = new ListNode(0);
        ListNode* cur = phead;
        while(cur1 || cur2 || sum)
        {
            if(cur1)
            {
                sum += cur1->val;
                cur1 = cur1->next;
            }

            if(cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }

            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            sum /= 10;
        }

        cur = phead->next;
        delete phead;

        return cur;
    }
};

//两数相加II（链表正序）
class Solution {
public:
    void reverse(ListNode*& head)
    {
        ListNode* p1 = nullptr;
        ListNode* p2=head,* p3 = head->next;

        while(p2)
        {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            if(p3)
                p3 = p3->next;
        }
        head = p1;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        reverse(l1);
        reverse(l2);
        ListNode* cur1 = l1,* cur2 = l2;
        int sum = 0;
        ListNode* phead = new ListNode(0);
        ListNode* cur = phead;
        while(cur1 || cur2 || sum)
        {
            if(cur1)
            {
                sum += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }

            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            sum /= 10;
        } 

        cur = phead->next;
        delete phead;
        reverse(cur);

        return cur;
    }
};

//两两交换链表中的节点（非递归）
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* phead = new ListNode(0);
        phead->next = head;
        ListNode* cur = phead;
        while(cur->next)
        {
            ListNode* next = cur->next;
            ListNode* Nnext = next->next;
            if(Nnext == nullptr)
                break;
            next->next = Nnext->next;
            Nnext->next =next;
            cur->next = Nnext;
            cur = next;
        }
        
        cur = phead->next;
        delete phead;

        return cur;
    }
};

//反转链表
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        if (head == nullptr)
            return nullptr;

        ListNode* p2 = head, * p1 = nullptr, * p3 = p2->next;
        while (p2)
        {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            if (p3)
                p3 = p3->next;
        }
        return p1;
    }
};

//链表内指定区间反转
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //哨兵位的头结点
        ListNode* phead = new ListNode(0);
        phead->next = head;
        ListNode* prev = phead;

        //找到待反转区间的前一个结点
        for (int i = 1; i < m; i++)
        {
            prev = prev->next;
        }

        //标记指定区间的第一个结点的下一个结点
        //把cur当前结点指向next结点的后一个结点
        //再把next结点指向prev的下一个结点
        //再把prev指向next结点
        //这样执行一次就把指定区间内的一个元素翻转到了前面
        ListNode* cur = prev->next, * next = cur->next;
        for (int i = m; i < n; i++)
        {
            next = cur->next;
            cur->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }

        cur = phead->next;
        delete phead;

        return cur;
    }
};

//合并两个排序的链表(用归并排序的思路)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* phead = new ListNode(0);
        ListNode* cur1 = pHead1, * cur2 = pHead2, * prev = phead;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next = cur2;
                cur2 = cur2->next;
            }
            prev = prev->next;
        }

        while (cur1)
        {
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
        }
        while (cur2)
        {
            prev->next = cur2;
            cur2 = cur2->next;
            prev = prev->next;
        }

        prev = phead->next;
        delete phead;
        return prev;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* phead = new ListNode(0);
        ListNode* cur1 = pHead1, * cur2 = pHead2, * prev = phead;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next = cur2;
                cur2 = cur2->next;
            }
            prev = prev->next;
        }

        while (cur1)
            prev->next = cur1;
        while (cur2)
            prev->next = cur2;

        prev = phead->next;
        delete phead;
        return prev;
    }

    ListNode* divide(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r)
            return nullptr;
        if (l == r)
            return lists[l];

        int mid = l + (r - l) / 2;

        ListNode* left = divide(lists, l, mid);
        ListNode* right = divide(lists, mid + 1, r);

        return Merge(left, right);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divide(lists, 0, lists.size() - 1);
    }
};

//合并k个已排序的链表
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* phead = new ListNode(0);
        ListNode* cur1 = pHead1, * cur2 = pHead2, * prev = phead;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next = cur2;
                cur2 = cur2->next;
            }
            prev = prev->next;
        }

        if (cur1)
            prev->next = cur1;
        else
            prev->next = cur2;

        prev = phead->next;
        delete phead;
        return prev;
    }

    ListNode* divide(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r)
            return nullptr;
        if (l == r)
            return lists[l];

        int mid = l + (r - l) / 2;

        ListNode* left = divide(lists, l, mid);
        ListNode* right = divide(lists, mid + 1, r);

        return Merge(left, right);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divide(lists, 0, lists.size() - 1);
    }
};


//判断链表中是否有环
class Solution {
public:
    bool hasCycle(ListNode* head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur)
        {
            if (s.count(cur))
            {
                return true;
            }
            s.insert(cur);
            cur = cur->next;
        }

        return false;
    }
};


//链表中环的入口结点
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set<ListNode*> s;
        ListNode* cur = pHead;
        while (cur)
        {
            if (s.count(cur))
                return cur;
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};


//链表中倒数最后k个结点
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* fast = pHead, * slow = pHead;
        while (k-- && fast)
        {
            fast = fast->next;
        }

        if (k >= 0)
            return nullptr;

        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};


//两个链表的第一个公共结点
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        ListNode* cur1 = pHead1, * cur2 = pHead2;
        while (cur1 != cur2)
        {
            cur1 = cur1 == nullptr ? pHead2 : cur1->next;
            cur2 = cur2 == nullptr ? pHead1 : cur2->next;
        }

        return cur1;
    }
};


//链表相加(二)
class Solution {
public:
    void reverse(ListNode*& pHead)
    {
        if (!pHead)
            return;

        ListNode* p2 = pHead, * p1 = nullptr, * p3 = p2->next;

        while (p2)
        {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            if (p3)
                p3 = p3->next;
        }
        pHead = p1;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* pHead = new ListNode(0);

        reverse(head1);
        reverse(head2);
        int sum = 0;
        ListNode* cur1 = head1, * cur2 = head2, * prev = pHead;
        while (cur1 || cur2 || sum)
        {
            if (cur1)
            {
                sum += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }

            prev->next = new ListNode(sum % 10);
            prev = prev->next;
            sum /= 10;
        }

        prev = pHead->next;
        delete pHead;
        reverse(prev);
        return prev;
    }
};


//单链表的排序
class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        ListNode* cur = head;
        vector<int> v;
        while (cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }

        sort(v.begin(), v.end());
        ListNode* pHead = new ListNode(0), * prev = pHead;
        for (auto x : v)
        {
            prev->next = new ListNode(x);
            prev = prev->next;
        }

        prev = pHead->next;
        delete pHead;

        return prev;
    }
};